package listes;

public class ListeDCE<F extends Comparable<F>> extends ListeDC<F> implements ListeE<F> {

	private static class IterateurDCE<E extends Comparable<E>> implements Iterateur<E> {
	    private ListeDC<E> liste;
	    private ListeDC<E>.Chainon next;
	    private ListeDC<E>.Chainon prev;
	    private ListeDC<E>.Chainon elementAccessible;
		
	    IterateurDCE(ListeDCE<E> l) {
	    	liste = l;
	    	next = l.tete;
	    	prev = null;
	    	elementAccessible = null;
	    }
	    
		public boolean hasNext()     { return next!=null; }
		public boolean hasPrevious() { return prev!=null; }
		
		public E next() throws java.util.NoSuchElementException {
			if(hasNext()) {
				elementAccessible = next;
				prev = next;
				next = next.suivant;
			}
			else throw new java.util.NoSuchElementException();
			return elementAccessible.valeur;
		}
		
		public E previous() throws java.util.NoSuchElementException {
			if(hasPrevious()) {
				elementAccessible = prev;
				next = prev;
				prev = prev.precedent;
			}
			else throw new java.util.NoSuchElementException();
			return elementAccessible.valeur;
		}
		
		public void remove() throws IllegalStateException {
			if(elementAccessible==null) throw new IllegalStateException();
			if(elementAccessible.precedent!=null) elementAccessible.precedent.suivant = elementAccessible.suivant;
			else liste.tete=elementAccessible.suivant; // ATTENTION : il faut dÃ©placer la tete
			if(elementAccessible.suivant!=null) elementAccessible.suivant.precedent = elementAccessible.precedent;
			else liste.queue=elementAccessible.precedent; // ATTENTION : il faut dÃ©placer la queue
			if(elementAccessible==next) next=next.suivant;
			else prev=prev.precedent;
			elementAccessible = null;
			// ATTENTION : mettre Ã  jour les autres attributs de la liste associÃ©e :
			liste.taille--;
			liste.courant = liste.tete;
			liste.indiceCourant = (liste.taille==0 ? -1 : 0);
		}
		
		public void set(E e) throws IllegalStateException {
			if(elementAccessible==null) throw new IllegalStateException();
			elementAccessible.valeur = e;
			elementAccessible = null;
		}
	}
	
	public ListeDCE()          { super();     }
	public ListeDCE(F... init) { super(init); }

	public void reverse() {
	/*	// Version inÃ©lÃ©gante et inefficace :
	    ListeDCE<F> aux = new ListeDCE<F>();
		for(int i=0; i<taille; i++) aux.add(0, get(i));
    	tete = aux.tete;
    	queue = aux.queue;
    	courant = aux.courant;
    	indiceCourant = aux.indiceCourant;
    	*/
	/*	// Inversion de valeurs (moins efficace Ã  cause de la gestion de l'indice :
		for(int i=0; i<taille/2; i++) {
			F aux = get(i);
			set(i, get(taille-1-i));
			set(taille-1-i, aux);
		}
		*/
	/*	// Inversion de valeurs :
		Chainon curseurDG;
		Chainon curseurGD;
		for(curseurDG = tete, curseurGD = queue; curseurDG!=curseurGD && curseurDG.suivant!=curseurGD;
			curseurDG = curseurDG.suivant, curseurGD = curseurGD.precedent) {
			F aux = curseurDG.valeur;
			curseurDG.valeur = curseurGD.valeur;
			curseurGD.valeur = aux;
		}
		*/
	    // Inverision de chaÃ®nage :
 		for(Chainon curseur = tete; curseur!=null; curseur = curseur.precedent) {
			Chainon aux = curseur.suivant;
			curseur.suivant = curseur.precedent;
			curseur.precedent = aux;
		}
		Chainon aux = tete;
		tete = queue;
		queue = aux;
		if(indiceCourant!=-1) indiceCourant = taille-1-indiceCourant;
 	}

	public Object[] toArray() {
		Object[] res = new Object[taille];
		int i; Chainon curseur; // variables de parcours
		for(curseur = tete, i=0; curseur!=null; curseur = curseur.suivant, i++)
			res[i] = curseur.valeur;
		return res;
	}
	
	public Iterateur<F> iterator() { return new IterateurDCE<F>(this); }

	public F max() throws java.util.NoSuchElementException {
		if(taille==0) throw new java.util.NoSuchElementException();
		F res = tete.valeur;
		for(Chainon curseur = tete.suivant; curseur!=null; curseur = curseur.suivant)
			if(res.compareTo(curseur.valeur)<0) res=curseur.valeur;	
		return res;
	}

	public F min() throws java.util.NoSuchElementException {
		if(taille==0) throw new java.util.NoSuchElementException();
		F res = tete.valeur;
		for(Chainon curseur = tete.suivant; curseur!=null; curseur = curseur.suivant)
			if(res.compareTo(curseur.valeur)>0) res=curseur.valeur;	
		return res;
	}

	public ListeE<F> subSet(F borneMin, F borneMax) {
		ListeE<F> res = new ListeDCE<F>();
		for(Chainon curseur = tete; curseur!=null; curseur = curseur.suivant)
			if(curseur.valeur.compareTo(borneMin)>=0 &&
			   curseur.valeur.compareTo(borneMax)< 0   ) res.add(curseur.valeur);	
		return res;
	}

	public void sort() {
		// Tri Ã  bulle (on peut largement mieux faire !)
		for(Chainon curseur = tete; curseur!=null; curseur = curseur.suivant)
			for(Chainon sousCurseur = curseur.suivant; sousCurseur!=null; sousCurseur = sousCurseur.suivant)
				if(curseur.valeur.compareTo(sousCurseur.valeur)>0) {
					F aux = curseur.valeur;
					curseur.valeur = sousCurseur.valeur;
					sousCurseur.valeur = aux;
				}
	}
	
	public static void main(String[] args) {
		ListeDCE<Integer> l1 = new ListeDCE<Integer>();
		System.out.print(l1+" renversÃ©e : "); l1.reverse(); System.out.println(l1); 
		l1 = new ListeDCE<Integer>(1);
		System.out.print(l1+" renversÃ©e : "); l1.reverse(); System.out.println(l1); 
		l1 = new ListeDCE<Integer>(1, -2, 17, 0, 15);
		System.out.print(l1+" renversÃ©e : "); l1.reverse(); System.out.print(l1);
		l1.reverse(); System.out.println(" re-renversÃ©e : "+l1); 
		
		ListeDCE<Integer> l2 = new ListeDCE<Integer>();
		System.out.print(l2+" en tableau : "); for(Object o : l2.toArray()) System.out.print("|"+o);
		System.out.println("|");
		l2 = new ListeDCE<Integer>(-10, -20, -30);
		System.out.print(l2+" en tableau : "); for(Object o : l2.toArray()) System.out.print("|"+o);
		System.out.println("|");
		
		l2 = new ListeDCE<Integer>(-10, 5, 7, 0, 0, -2, 18, 53, 32, -41, -30);
		Iterateur<Integer> it1 = l2.iterator();
		Iterateur<Integer> it2 = l2.iterator();
		while(it1.hasNext()) it1.next();
		System.out.println("Parcours de : "+l2+" :");
		for(int i=0; i<l2.size(); i++) {
			it1.hasPrevious();
			it2.hasNext();
			System.out.println(l2.get(i)+" "+it1.previous()+" "+it2.next());
		}
		it1 = l2.iterator();
		System.out.println("Suppression des nombres nÃ©gatifs et incrÃ©ment des nombres pairs dans "+l2+" :");
		while(it1.hasNext()) {
			Integer val = it1.next();
			if(val<0) it1.remove();
			else if(val%2==0) it1.set(val+1);
		}
		System.out.println("-> "+l2+" (tete : "+l2.tete.valeur+" ; queue : "+l2.queue.valeur+")");
		
		l2 = new ListeDCE<Integer>(-10, 5, 7, 0, 0, -2, 18, 53, 32, -41, -30);
		System.out.println("maximum / minimum dans "+l2+" : "+l2.max()+" / "+l2.min());
		System.out.println("sous-ensemble compris entre -30 et 7 dans "+l2+" : "+l2.subSet(-30, 7));

		System.out.print(l2+" triÃ©e : "); l2.sort(); System.out.println(l2);
		/*
			( ) renversÃ©e : ( )
			( 1 ) renversÃ©e : ( 1 )
			( 1 -2 17 0 15 ) renversÃ©e : ( 15 0 17 -2 1 ) re-renversÃ©e : ( 1 -2 17 0 15 )
			( ) en tableau : |
			( -10 -20 -30 ) en tableau : |-10|-20|-30|
			Parcours de : ( -10 5 7 0 0 -2 18 53 32 -41 -30 ) :
			-10 -30 -10
			5 -41 5
			7 32 7
			0 53 0
			0 18 0
			-2 -2 -2
			18 0 18
			53 0 53
			32 7 32
			-41 5 -41
			-30 -10 -30
			Suppression des nombres nÃ©gatifs et incrÃ©ment des nombres pairs dans ( -10 5 7 0 0 -2 18 53 32 -41 -30 ) :
			-> ( 5 7 1 1 19 53 33 ) (tete : 5 ; queue : 33)
			maximum / minimum dans ( -10 5 7 0 0 -2 18 53 32 -41 -30 ) : 53 / -41
			sous-ensemble compris entre -30 et 7 dans ( -10 5 7 0 0 -2 18 53 32 -41 -30 ) : ( -10 5 0 0 -2 -30 )
			( -10 5 7 0 0 -2 18 53 32 -41 -30 ) triÃ©e : ( -41 -30 -10 -2 0 0 5 7 18 32 53 )
		 */
	}

}
